#include <iostream>
#include "SortTestHelper.h"
#include "InsertionSort.h"

using namespace std;
template <typename  T>
void __Merge(T arr[],int l,int mid,int r){
      T temp[r-l+1];
    for(int i=l;i<=r;i++)
            temp[i-l]=arr[i];
    int i=l,j=mid+1;

    for (int k = l; k <= r; k++) {
        if (i > mid) {
            arr[k]=temp[j-l];
            j ++;
        } else if (j>r) {
            arr[k]=temp[i-l];
            i ++;
        }
        else if (temp[i - l] < temp[j - l]) {
            arr[k]=temp[i-l];
            i ++;
        } else{
            arr[k]=temp[j-l];
            j ++;
        }
    }

}

template <typename  T>
void __mergeSort(T arr[],int l,int r){

//    if(l>=r)
//        return;
    if(r-l<=15) {
        insertionSort(arr,l,r);
        return;
    }

    int mid=(l+r)/2;
    __mergeSort(arr,l,mid);
    __mergeSort(arr,mid+1,r);
    if(arr[mid]>arr[mid+1])
    __Merge(arr,l,mid,r);
}

template <typename T>
void mergeSort(T arr[],int n){

    __mergeSort(arr,0,n-1);
}

int main() {
   int n=50000;
    cout<<"Test for random array, size = "<<n<<", random range [0, "<<n<<"]"<<endl;
    int* arr1=SortTestHelper::generateRandomArray(n,0,n);
    int* arr2=SortTestHelper::copyIntArray(arr1,n);
    SortTestHelper::testSort("Insertion Sort", insertionSort, arr1, n);
    SortTestHelper::testSort("Merge Sort", mergeSort,arr2,n);
    delete[] arr1;
    delete[] arr2;
    cout<<endl;


    // 测试2 测试近乎有序的数组
    // 对于近乎有序的数组, 数组越有序, InsertionSort的时间性能越趋近于O(n)
    // 所以可以尝试, 当swapTimes比较大时, MergeSort更快
    // 但是当swapTimes小到一定程度, InsertionSort变得比MergeSort快
    int swapTimes = 26;
    assert( swapTimes >= 0 );

    cout<<"Test for nearly ordered array, size = "<<n<<", swap time = "<<swapTimes<<endl;
    arr1 = SortTestHelper::generateNearlyOrderedArray(n,swapTimes);
    arr2 = SortTestHelper::copyIntArray(arr1, n);

    SortTestHelper::testSort("Insertion Sort", insertionSort, arr1, n);
    SortTestHelper::testSort("Merge Sort",mergeSort,arr2, n);

    delete[] arr1;
    delete[] arr2;
    return 0;
}